% chktex-file 1
% chktex-file 2
% chktex-file 12
% chktex-file 36

\documentclass[a4paper, 12pt]{ctexart}

\usepackage{geometry}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage[thmmarks, amsmath]{ntheorem}
\usepackage{graphicx}
\usepackage{booktabs}
\usepackage{authblk}
\usepackage{titlesec}
\usepackage{setspace}
\usepackage[linewidth=1pt]{mdframed}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{float}
\usepackage{xcolor}
\usepackage[titletoc]{appendix}
\usepackage{hyperref}
\usepackage{cleveref}
\usepackage{fancyhdr}
\usepackage{abstract}
\usepackage{pgfplots}
\usepackage[
    backend = bibtex,
    style = numeric,
    citestyle = ieee
]{biblatex}

% Graphs
\usepackage{tikz}
\usetikzlibrary{backgrounds}
\usetikzlibrary{patterns}
\usetikzlibrary{fadings}
\usepackage{fig_problem}
\usepackage{fig_gzjn}
\usepackage{fig_gzjnext}
\usepackage{fig_design}
\usepackage{fig_interest}

% Our packages
\usepackage{preloads}
\usepackage{easy_tikz_figure}

\addbibresource{ref.bib}

% --------------------------------------

\title{\textbf{日历拼图游戏的设计规律}}

\author{郑铭稼}
\affil{上海市西南位育中学}
\renewcommand\Authands{, }

\date{\today}

\begin{document}

\pagenumbering{gobble}
\maketitle

\begin{abstract}
\vspace{1em}
本文讨论了一类基于全覆盖问题的拼图游戏，由类似多米诺骨牌问题的干支纪年拼图游戏引入，探索了格差对游戏可解性的影响. 
后将问题推广到正三角形网格中，总结了该类游戏的设计规律，并根据该规律设计了一套底板与组件，使用 Python 语言编写了 DFS 算法搜索解的数量. 
最后参考麦克斯韦方程的形式，建立了难度与趣味性的函数关系，构建了难度的量化指标，再转化为趣味性指标，以检验先前的设计.

\vspace{1em}
\noindent\textbf{关键词：} 拼图问题，设计规律，趣味性.
\end{abstract}

\newpage
\tableofcontents

% --------------------------------------
\newpage
\pagenumbering{arabic}

\section{问题描述}\label{sec:problem_description}

本文讨论的拼图游戏问题来源于笔者参与的第三届上海市中学数学学术展评活动，内容有删改，问题如下：

考虑一类拼图游戏: 在一个网格区域中, 选定其中部分子区域作为目标区域, 
用给定的组件将余下的部分铺满. 在拼图过程中允许对组件进行适当的平移, 旋转, 翻转操作.

1. 如\cref{fig:pd:GZJN}(a) 所示的干支纪年拼图游戏采用 10 块面积为 2 的组件 (假定每个单位正方形
的面积为 1). 要求将指定年份对应的方格留空, 其余方格皆铺满, 以此拼出指定的年份.
例如, \cref{fig:pd:GZJN}(b) 给出了甲辰年的一种拼法. \\
证明: 干支纪年的 60 种组合皆可在此拼图游戏中拼出.

\EasyTikzFigure[
    scale = 0.6,
    label = fig:pd:GZJN
]{
    \drawGZJN / 干支纪年拼图游戏
}

2. 如\cref{fig:pd:APuzzleADay} 所示是 DragonFjord 公司的 A puzzle a day 拼图游戏，
采用 7 块面积为 5 的组件和 1 块面积为 6 的组件拼出指定的公历日期，我们仍可以证明公历日期的 366 种组合皆可拼出.

我们的目标是使用数学方法总结此类拼图游戏的设计规律，并保证游戏的可解性（即每个公历日期都可以拼出）.

\EasyTikzFigure[
    scale = 0.6,
    label = fig:pd:APuzzleADay
]{
    \drawAPuzzleADay / DragonFjord 公司的 A puzzle a day 日历拼图游戏
}

3. 根据此前总结的设计规律为如\cref{fig:pd:triangle} 所示的正三角形网格设计一款日历拼图游戏.
首先从 54 个小三角形中剔除 4 个, 由余下 50 个小三角形形成拼图区域, 再将 “1 月”
至 “12 月”, “1 日” 至 “31 日”, “周日” 至 “周六” 以适当的方式排布于这 50 格中. 在此
基础上设计一套拼图组件 (共需覆盖 47 个小三角形, 留出 “月份”, “日期”, “星期” 3 个
空位). 

\EasyTikzFigure[
    label = fig:pd:triangle
]{
    \drawTriangleGrid / 正三角形网格下的日历拼图游戏
}

% --------------------------------------
\newpage

\section{拼图问题初探——干支纪年拼图游戏}\label{sec:GZJN}

首先注意到十天干与十二地支的配对关系，“甲丙戊庚壬”只能与“子寅辰午申戌”组合，“乙丁己辛癸”
只能与“丑卯巳未酉亥”组合，这也验证了题中的 60 种组合，而非$12\times 10=120$种组合.

我们容易想到将配对的 2 组天干地支分开，类似国际象棋的棋盘，我们将底板涂上间隔的颜色，如\cref{fig:GZJN:stained}.

\EasyTikzFigure[
    label = fig:GZJN:stained,
    caption = 涂色的底板
]{
    \drawBoardGZJN\drawColorGZJN\drawLabelGZJN / 
}

\textit{注}：下文我们将问题转化为图论问题，以便更加清晰、严谨地证明我们的结论，但这不是本文讨论的重点，因此下文关于图论的说理是简略的.

我们将底板抽象成一个无向图：将每个方格用一个节点表示，若两个方格有公共边，
则认为对应的两个节点之间有边相连，称两个节点是相邻的.

\cref{fig:GZJN:stained} 的涂色过程实际上是图论中的\textbf{2-染色}问题. 在染色后的图中，
我们找到一条特殊的\textbf{哈密尔顿回路}(Hamiltonian cycle)，如\cref{fig:GZJN:cycle}.

\EasyTikzFigure[
    label = fig:GZJN:cycle,
    caption = 哈密尔顿回路
]{
    \drawCycleGZJN / 
}

我们有以下基本思路： \\
\indent 1. 删去任意两个异色的节点后剩下的路长度为偶数. \\
\indent 2. 对于长度为偶数的路，我们按顺序每 2 个节点放一个组件，即可铺满这条路.

\begin{proposition}\label{prop:GZJN:GZJN}
    对于上述的哈密尔顿回路，删去任意两个异色的节点，剩下的部分总是可以用题目所给的$10$个$2\times 1$组件拼出.
\end{proposition}

命题\ref{prop:GZJN:GZJN} 包含了如“乙丙”这样非法的天干地支组合，比原命题更强，
具有充分性，因此我们证明了原命题.

% --------------------------------------
% \newpage

\section{干支纪年拼图游戏的拓展}\label{sec:GZJNext}

命题\ref{prop:GZJN:GZJN} 中包含的非法组合为我们提供了指引，那么是否任意删去两个节点，
剩下的部分都可以被拼出呢?

直接观察\cref{fig:GZJN:stained}，显然对于“甲丙”的组合，“乙”被关在了角落里，
类似地“子寅”、“酉亥”、“申戌”、“庚壬”都无法拼出，那么剩下的组合都可以被拼出吗? 又如何证明呢?

使用路长度的奇偶性仍然可以证明这个命题，但略微繁琐，于是我们介绍另一种思路\upcite{golomb1996polyominoes}：

首先进行\textbf{2-染色}，之后观察到底板中黑白格的数量是相等的，而给定的 2 格组件一定覆盖一黑一白格，
这样无论我们放多少个组件，剩余的黑白格的数量总是相等的. 若我们删去 2 个同色格，则黑白格的数量就不相等，
不断摆放组件直到剩 2 个格子，易知这 2 个格子同色，因此无法用一个 2 格组件覆盖. 故我们无法拼出 2 个同色格的组合.

现有的大多文献研究的是正方形网格下的多米诺骨牌问题\upcite{GOLOMB1966280}，下文我们主要讨论正三角形网格下的类似问题.

% --------------------------------------
% \newpage

\section{设计规律的分析与总结}\label{sec:design}

\numberwithin{theorem}{subsection}
\numberwithin{proposition}{subsection}
\numberwithin{lemma}{subsection}
\numberwithin{corollary}{subsection}
\numberwithin{figure}{subsection}
\numberwithin{equation}{subsection}

% --------------------------------------
\subsection{底板的设计}\label{subsec:des_board}

底板的设计分为剔除 4 个格子与排布“月份”, “日期”, “星期”格. 最初我们模仿了 A puzzle a day 游戏中的底板设计，
剔除了右上方的 4 个格子，将月份格集中排布与前 2 行，日期格集中在中间行，星期格集中在最后一行，
如\cref{fig:bdesign:des_apad}(a).

\begin{figure}[H]
    \centering
    \begin{subfigure}[b]{0.45\textwidth}
        \centering
        \includegraphics[width=\linewidth]{./graphs/des_apad.png}
        \caption{最初设计}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.25\textwidth}
        \centering
        \includegraphics[width=\linewidth]{./graphs/ex_p1t.png}
        \caption{“单格”情况}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.25\textwidth}
        \centering
        \includegraphics[width=\linewidth]{./graphs/ex_p2t.png}
        \caption{“双格”情况}
    \end{subfigure}
    \caption{}\label{fig:bdesign:des_apad}
\end{figure}

我们发现要想拼出 May 2 组合，必须使用 1 格组件覆盖 Apr，我们称 Apr 为“单格”，如\cref{fig:bdesign:des_apad}(b). 
同样地，对于 Fri 30 组合，我们必须使用 2 格组件覆盖 Sat Sun（不考虑使用 2 个 1 格组件），我们称 Sat Sun 为“双格”，如\cref{fig:bdesign:des_apad}(c).

若两个格子$A,\,B$有公共边，则称$A,\,B$是相邻的，$A,\,B$互为邻居. 对于由若干相邻格组成的区域$C$，我们称$C$中所有格的邻居的集合
（集合中不包含$C$中的格子）为区域$C$的邻居.

“单格”的严格定义为：对于格$A$，若$A$的任意两个邻居是不同类型（“月份”,“日期”,“星期”），则$A$是“单格”. 
同理我们再定义“双格”：对于 2 格区域$C$，若$C$的任意两个邻居是不同类型，则$C$是“双格”.

我们认为引入 1 格，2 格组件导致组件放置的灵活性大幅提高，从而降低了游戏难度，因此我们考虑避免“单格”，“双格“情况. 

\begin{figure}[H]
    \centering
    \begin{subfigure}[b]{0.45\textwidth}
        \centering
        \includegraphics[scale = 0.4]{./graphs/thm_single.png}
        \caption{}
    \end{subfigure}
    % \hfill
    \begin{subfigure}[b]{0.45\textwidth}
        \centering
        \includegraphics[scale = 0.4]{./graphs/thm_single_colored.png}
        \caption{}
    \end{subfigure}
    \caption{}\label{fig:thm:single}
\end{figure}

\begin{theorem}\label{thm:bdesign:single}
    如上图，若不出现“单格”，“双格”情况，则底板边缘的一圈除了 d,\,X,\,S,\,N,\,F，其他格子都是日期格.
\end{theorem}

\begin{proof}.\\
\indent 用字母对底板边缘格进行编号，如\cref{fig:thm:single}(a)，注意到格 U 只有 V,\,T 2 个邻居，为了使 U 不是“单格”，
则 V,\,T 一定是同类格. 同理可得 V,\,T,\,R,\,P 都是同类格.
如\cref{fig:thm:single}(b)，其中同色的格子是同类的. \\
\indent 再考虑上方拐角处的 A,\,B,\,C,\,D，为了使 B,\,C 不是“双格”，A,\,D 必须同类，
进而 D,\,C,\,B,\,A,\,e,\,b,\,Z 都是同类的. 同理沿着边缘，按逆时针方向递推，则底板边缘的一圈除了 d,\,X,\,S,\,N,\,F，其他格子都是同类的. \\
\indent 而上述的同类格有 25 个，满足数量的只有日期格，因此这些格子都是日期格.
\end{proof}

\begin{figure}[H]
    \centering
    \begin{subfigure}[b]{0.45\textwidth}
        \centering
        \includegraphics[scale = 0.4]{./graphs/des_sur.png}
        \caption{日期格的排布}
    \end{subfigure}
    % \hfill
    \begin{subfigure}[b]{0.45\textwidth}
        \centering
        \includegraphics[scale = 0.4]{./graphs/des_sur_colored.png}
        \caption{}
    \end{subfigure}
    \caption{}\label{fig:bdesign:des_sur}
\end{figure}

我们不妨在 d,\,X,\,S,\,N,\,F 也填入日期格，如\cref{fig:bdesign:des_sur}(a). 接下来考虑排布与 30 个边缘日期格相邻的“内圈”格，“内圈”格在\cref{fig:bdesign:des_sur}(a)中已经用字母标出，剩下的三个格子用符号标注. 
由于“内圈”格不在底板边缘，因此任意两个相邻的“内圈”格组成的区域必定有 4 个邻居，则至少有 2 个邻居是同类的，故“内圈”格不会出现“双格”情况. 

接下来从格 u 开始考虑，u 已经有一个邻居 11，为使 u 不是“单格”，v ,\, t 是同类的或 v ,\, t 中有一个是日期格 31，
我们先不考虑比较特殊的日期格 31，因此可得t,\,v,\,x 同类. 同理，如\cref{fig:bdesign:des_sur}(b)，其中同色的格子是同类的. 

我们找到一种符合上述的排布，先间隔排布月份格，如\cref{fig:bdesign:inner}(a)，
剩下的 8 个“内圈”格正好填入 7 个星期格与日期格 31，如\cref{fig:bdesign:inner}(b).

\begin{figure}[H]
    \centering
    \begin{subfigure}[b]{0.45\textwidth}
        \centering
        \includegraphics[scale = 0.4]{./graphs/des_inner_a.png}
        \caption{}
    \end{subfigure}
    % \hfill
    \begin{subfigure}[b]{0.45\textwidth}
        \centering
        \includegraphics[scale = 0.4]{./graphs/des_inner_b.png}
        \caption{}
    \end{subfigure}
    \caption{}\label{fig:bdesign:inner}
\end{figure}

最后我们填入剩下的 3 个月份格，得到最终的底板设计，如\cref{fig:bdesign:final}.

\begin{figure}[H]
    \centering
    \includegraphics[scale=0.7]{./graphs/des_final.png}
    \caption{最终的底板设计}\label{fig:bdesign:final}
\end{figure}

% --------------------------------------
\subsection{组件的设计}\label{subsec:des_comp}

参照第 \ref{sec:GZJNext} 节 \nameref{sec:GZJNext}，我们先考量 A puzzle a day 游戏中的黑白格数量差距（以下我们称这种差距为“格差”）.

将\cref{fig:pd:APuzzleADay} 中的底板进行\textbf{2-染色}，由于底板有 43 个格子，此时格差为 1.
当留空的 2 个格子异色时，格差仍然为 1; 当 2 个格子同色时，格差可以达到 3.
而 7 块面积为 5 的组件每块提供 1 格差，面积为 6 的组件提供 0 格差.
因此我们最多可以提供 7 格差，而底板只接受 1 或 3 格差.

这说明我们的组件会互相抵消格差，如\cref{fig:cdesign:cdiff} 的情况.

\EasyTikzFigure[
    label = fig:cdesign:cdiff,
    caption = 抵消格差的组件
]{
    \drawCellDiffExampleLeft / ,
    \drawCellDiffExampleRight / 
}

\textit{注}：我们将拼出某个日期组合看作从底板上挖去对应的格子，因此底板的格差随着日期组合不同而变化，我们称其中最大的为底板的最大格差.

按照第 \ref{sec:GZJNext} 节中的讨论，我们得出以下结论：若游戏可解，则底板的最大格差小于等于所有组件的格差和. 
那么格差和是否越大越好呢?
我们不妨考虑以下两种情况，其中我们假设底板的最大格差为 3：\vspace{1em}\\
\indent A. 3 个格差为 1 的组件，5 个格差为 0 的组件. \\
\indent B. 8 个格差为 1 的组件.

当底板取得最大格差 3 时，情况 A 的 3 个 1 格差组件必须各自不相邻
（认为两个 1 格差组件相邻时会抵消格差）；而情况 B 8 个组件可以任意相邻摆放. 
因此情况 B 的不确定性（组件摆放的可能性）更高，我们认为这种情况是更优的，即我们希望所有组件的格差和越大越好.

在第 \ref{subsec:des_board} 节的讨论中，我们保证底板不会出现“单格”，“双格”的情况，以减少灵活性，提高游戏难度，因此我们不考虑 1 格、2格组件. 
我们还需考虑组件的数量，这里我们认为组件的面积差异不宜过大（详见第 \ref{sec:interest} 节 \nameref{sec:interest}），
组件面积平均为 6 比较合理，组件的面积和应为 47，因此组件数量为 8\,\textasciitilde\,10.

\begin{figure}[H]
    \begin{mdframed}
        \centering
        \begin{subfigure}[b]{0.2\textwidth}
            \centering
            \includegraphics[scale = 0.4]{./graphs/comps1/1.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.2\textwidth}
            \centering
            \includegraphics[scale = 0.4]{./graphs/comps1/2.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.2\textwidth}
            \centering
            \includegraphics[scale = 0.4]{./graphs/comps1/3.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.2\textwidth}
            \centering
            \includegraphics[scale = 0.4]{./graphs/comps1/4.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.2\textwidth}
            \centering
            \includegraphics[scale = 0.4]{./graphs/comps1/5.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.2\textwidth}
            \centering
            \includegraphics[scale = 0.4]{./graphs/comps1/6.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.2\textwidth}
            \centering
            \includegraphics[scale = 0.4]{./graphs/comps1/7.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.2\textwidth}
            \centering
            \includegraphics[scale = 0.4]{./graphs/comps1/8.png}
        \end{subfigure}
    \end{mdframed}
    \caption{初步的组件设计}\label{fig:cdesign:comps1}
\end{figure}

% --------------------------------------
\subsection{可解性的验证}\label{subsec:solvable}

我们并未找到游戏可解的充要条件，上述的约束条件皆为必要条件，因此我们使用 DFS 算法来搜索 2562 种日期组合的解.

使用\cref{fig:bdesign:final}\,的底板与\cref{fig:cdesign:comps1}\,的组件，经过程序验证，共有 130 种日期组合不可解，例如 Jan 5 Mon、Nov 11 Sun，
观察底板，如\cref{fig:solvable:uns}，注意到这种组合形成较窄的区域，无法用现有的 8 块较大的组件覆盖，因此我们考虑将现有的较大组件拆分成较小的组件，
将\cref{fig:solvable:cadjust}(a)中的组件删去，引入\cref{fig:solvable:cadjust}(b)中的 3 个组件.

\begin{figure}[H]
    \centering
    \begin{subfigure}[b]{0.45\textwidth}
        \centering
        \includegraphics[scale=0.7]{./graphs/uns_a.png}
        \caption{}
    \end{subfigure}
    % \hfill
    \begin{subfigure}[b]{0.45\textwidth}
        \centering
        \includegraphics[width=\linewidth]{./graphs/uns_b.png}
        \caption{}
    \end{subfigure}
    \caption{}\label{fig:solvable:uns}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{mdframed}
        \begin{minipage}[t]{\textwidth}
            \begin{flushleft}
                \textbf{(a)}
            \end{flushleft}
            \centering
            \includegraphics[scale = 0.5]{./graphs/comps1/4.png}
            \includegraphics[scale = 0.5]{./graphs/comps1/7.png}
        \end{minipage}
        \hfill
        \begin{minipage}[t]{\textwidth}
            \centering
            \tikz\draw[thick] (0,0) -- (12.5,0);
        \end{minipage}
        \hfill
        \begin{minipage}[t]{\textwidth}
            \begin{flushleft}
                \textbf{(b)}
            \end{flushleft}
            \centering
            \includegraphics[scale = 0.5]{./graphs/comps2/1.png}
            \includegraphics[scale = 0.5]{./graphs/comps2/2.png}
            \includegraphics[scale = 0.5]{./graphs/comps2/6.png}
        \end{minipage}
    \end{mdframed}
    \caption{组件调整}\label{fig:solvable:cadjust}
\end{figure}

于是有最终的组件设计，如\cref{fig:solvable:final_des}.

\begin{figure}[H]
    \begin{mdframed}
        \centering
        \begin{subfigure}[b]{0.3\textwidth}
            \centering
            \includegraphics[scale = 0.3]{./graphs/comps2/1.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.3\textwidth}
            \centering
            \includegraphics[scale = 0.3]{./graphs/comps2/2.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.3\textwidth}
            \centering
            \includegraphics[scale = 0.3]{./graphs/comps2/3.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.3\textwidth}
            \centering
            \includegraphics[scale = 0.3]{./graphs/comps2/4.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.3\textwidth}
            \centering
            \includegraphics[scale = 0.3]{./graphs/comps2/5.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.3\textwidth}
            \centering
            \includegraphics[scale = 0.3]{./graphs/comps2/6.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.3\textwidth}
            \centering
            \includegraphics[scale = 0.3]{./graphs/comps2/7.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.3\textwidth}
            \centering
            \includegraphics[scale = 0.3]{./graphs/comps2/8.png}
        \end{subfigure}
        \begin{subfigure}[b]{0.3\textwidth}
            \centering
            \includegraphics[scale = 0.3]{./graphs/comps2/9.png}
        \end{subfigure}
    \end{mdframed}
    \caption{最终组件设计}\label{fig:solvable:final_des}
\end{figure}

再次通过程序验证，所有日期均可解. 接着我们将解的数量绘制成直方图，如\cref{fig:solvable:sol_dist}，
对于 2562 种日期组合，平均解数量为 708 种，最少解的组合为 Sep 25 Wed，仅 14 种；最多解的组合为 May 1 Thu，有 2752 种.

\begin{figure}[H]
    \centering
    \includegraphics[scale=0.55]{./graphs/sol_dist.png}
    \caption{解数量的分布}\label{fig:solvable:sol_dist}
\end{figure}

% --------------------------------------
% \newpage

\section{趣味性指标的量化}\label{sec:interest}

游戏的趣味性是比较主观的指标，这里我们认为该类拼图游戏的趣味性仅与游戏难度有关. 以下我们构造趣味性的量化指标.

% --------------------------------------
\subsection{难度指标}\label{subsec:qdif}

我们考虑与游戏难度有关的特征：
\begin{itemize}

    \item 解的数量的均值$\bar{N}_{S}$

解的数量与游戏难度有直接关系，我们认为解的数量与游戏难度负相关，可以使用解的数量的均值作为特征. 
在确保游戏可解时，$\bar{N}_{S} \ge 1$.

    \item 组件的不规则程度$R$

我们认为组件越不规则，拼图的难度越高. 而当面积不变时，二维图形的凸起越多，图形越不规则，
考虑使用图形的凸包面积，这直观的反映图形的凸起程度。我们先使用Andrew's Monotone Chain二维凸包算法找到图形的凸包（Convex Hull），
再使用高斯面积公式（鞋带公式, Shoelace Formula）求得凸包的面积.

于是有$R$的计算公式$R = \frac{H}{S}$，其中$H$为凸包面积，$S$为组件的面积. 根据凸包的定义，我们可知$H \ge S$，故$R \ge 1$. 我们将$R$作如下修正，使得$R \ge 0$，以方便后续的计算.

\[
R = \frac{H}{S} - 1
\]

    \item 组件面积的方差$V_{C}$

在实际游玩过程中，我们倾向于优先选择面积较大的组件，因此我们认为：$V_{C}$越小，组件面积越平均，
游玩时不易作出选择，游戏难度更大.

\end{itemize}

构建游戏难度$D$的计算公式：

\begin{equation}
    D = \frac{1}{\lg (\bar{N}_{S} + 1)} + \bar{R} + V_{C}
\end{equation}\label{eqn:qdif}

其中，参考\cref{fig:solvable:sol_dist} 解数量的分布，$\bar{N}_{S}$数量级较大，于是取以 10 为底的对数，再取倒数满足解的数量与游戏难度负相关. 
我们认为一般情况下$\bar{N}_{S}$远大于 1，考虑到极端值$\bar{N}_{S} = 1$使得分母为 0，我们将$\bar{N}_{S}$加 1；$\bar{R}$是组件的不规则程度的平均值. 
以上的 3 个变量均为无量纲数，因此$D$是无量纲数，且$D > 0$.

% --------------------------------------
\subsection{趣味性指标}\label{subsec:qi}

我们的目标是找到一个函数$I(D)$，将游戏难度$D$转换为趣味性$I_{ntr}$. 我们考虑$I(D)$应满足：
\begin{itemize}
    \item 游戏太难或太易都导致游戏失去趣味，因为$D > 0$，因此有$D \to 0 ,\; I(D) \to 0$ ；\; $D \to +\infty ,\; I(D) \to 0$.

    \item $I(D)$先增大后减小，引入一个参数$\mu$，认为游戏难度$D=\mu$时游戏最具有趣味，因此有$\max I(D) = I(\mu)$.
\end{itemize}

受到麦克斯韦速率分布函数的启发，我们考虑以下的形式：
\begin{equation}
    \phi(x) = e^{-\frac{x^2}{A}}x^2
\end{equation}
\begin{equation}
    \phi'(x) = e^{-\frac{x^2}{A}}(-\frac{2}{A}x^3+2x)
\end{equation}

将$\phi'(\mu) = 0$代入：
\begin{align*}
    e^{-\frac{\mu^2}{A}}(-\frac{2}{A}\mu^3+2\mu) = 0 \\
    -\frac{2}{A}\mu^3+2\mu = 0
\end{align*}
因此有：
\begin{equation}
    A = \mu ^ 2
\end{equation}
最后我们将$\phi(x)$归一化，使其值域为$[0,1]$，得到$I(D)$的表达式：
\begin{equation}
    I(D) = \frac{\phi(D)}{\phi(\mu)} 
    = \frac{e^{-\frac{D^2}{\mu^2}}D^2}{\frac{1}{e}\mu^2} 
    = \frac{e}{\mu^2} e^{-\frac{D^2}{\mu^2}}D^2 \quad (D \ge 0)
\end{equation}

\EasyTikzFigure[
    caption = $I(D)$的大致图像,
    label = fig:interest:ID
]{
    \drawID / 
}

$I(D)$的图像大致如\cref{fig:interest:ID}，观察到$I'(D)$有两个峰，记为$D=\alpha$与$D=\beta$，$I'(D)$在$\alpha$与$\beta$附近绝对值较大，
意味着原函数$I(D)$在$\alpha$与$\beta$附近变化较快，即难度$D$在$\alpha$与$\beta$附近时，趣味性$I_{ntr}$随难度$D$变化较快.

于是我们考虑求出$\alpha$与$\beta$的值. 令$I''(D)=0$，$D=\alpha$与$D=\beta$是方程的两根，且$0 < \alpha < \beta$，有：
\[
    I''(D) = \frac{e}{\mu^2} e^{-\frac{D^2}{A}} (\frac{4}{A^2}D^4 - \frac{10}{A}D^2 + 2)
\]
\[
    \frac{4}{A^2}D^4 - \frac{10}{A}D^2 + 2 = 0
\]
\[
    (D^2 - \frac{5}{4}A)^2 = \frac{17}{16}A^2
\]
\[
    D^2 = \frac{5 \pm \sqrt{17}}{4}A
\]
最终有：
\begin{equation}
    \alpha = \sqrt{\frac{5 - \sqrt{17}}{4}A} \;, \quad \beta = \sqrt{\frac{5 + \sqrt{17}}{4}A}
\end{equation}

% --------------------------------------
\subsection{模型检验}\label{subsec:m_validation}

由于趣味性较主观，因人而异，因此我们无法确定参数$\mu$的值. 这里我们可以代入第 \ref{sec:design} 节中的设计，
如\cref{fig:solvable:final_des}，有
$\bar{N}_{S} = 708.897 ,\, \bar{R} = 0.166 ,\, V_{C} = 0.157$，
计算得$D = 0.674$.

% --------------------------------------
\subsection{模型的优缺点}\label{subsec:m_advantage}

我们只考虑了难度与趣味性的直接关系，并且其中缺少与底板有关的特征，对于底板的形状、月份,日期,星期格的排布等这类特征，
我们将其归类为“设计”因素，是本文没有考虑的.

% --------------------------------------
% \newpage

\section{总结与不足}\label{sec:summary}

在第 \ref{sec:GZJN} 节 \nameref{sec:GZJN} 中，我们将问题转化为图论问题，之后找到一条哈密尔顿回路，再利用奇偶性证明原命题. 
接着我们在第 \ref{sec:GZJNext} 节 \nameref{sec:GZJNext} 中讨论并引出了格差的概念.

在第 \ref{sec:design} 节 \nameref{sec:design} 中，我们先模仿了 A puzzle a day 游戏中的底板设计，分析其运用在正三角形网格上的问题，
通过避免“单格”、“双格”，设计出一个底板；随后运用格差，设计了一套组件. 通过 Python 程序验证，发现初次设计的拼图游戏有不可解的情况，
于是我们又进行调整，最后得出一版设计.

在第 \ref{sec:interest} 节 \nameref{sec:interest} 中，对游戏趣味性进行量化. 先找到与游戏难度相关的特征，并给出游戏难度$D$的计算公式，
再通过引入一个函数$I(D)$，将难度$D$变换为趣味性$I_{ntr}$，根据我们考虑的$I(D)$特征，我们联想到麦克斯韦速率分布方程，模仿其形式构造了$I(D)$.

第 \ref{sec:design} 节中关于格差只能定性分析，暂时没有定量分析的方法；
除了正三角形、正方形网格，我们还可拓展到正偶数边形网格\upcite{CONWAY1990183}，探究上述结论是否仍然成立.

% --------------------------------------
% \newpage

\section{写在最后}\label{sec:the_end}

% 我要感谢支持我的老师们，其中我要特别感谢袁昳桢老师，

% 在这短时间的研究中，我感受到成功的喜悦，也遭到

% 8 月 21 日下午有机会在决赛现场观摩，收获颇丰，特别是有幸听到了出题人邵美悦研究员
% 的解析，方法实在巧妙，于是笔者整理后写成了这篇文章.

% --------------------------------------
% \newpage

\printbibliography[title={参考文献}]

\end{document}